#include "util.h"
#include "common_sort.h"


void QuickSort::sort(std::vector<int>& vec) {
	int sz = vec.size();
	if (sz <= 1) {
		return;
	}

	int start = 0;
	int end = sz - 1;
	quickSort(vec, start, end);
}

int QuickSort::partition(std::vector<int>& vec, int start, int end) {
	int index = start;
	int pivot = vec[index];

	int sz = vec.size();

	while (start < end) {
		while (start < sz && vec[start] <= pivot) {
			++start;
		}

		while (end > 0 && vec[end] > pivot) {
			--end;
		}
		
		if (start < end) {
			util::swap(vec, start, end);
		}
	}

	if (index != end) {
		util::swap(vec, index, end);
	}
	return end;
}

void QuickSort::quickSort(std::vector<int>& vec, int start, int end) {
	if (start >= end) {
		return;
	}

	int pi = partition(vec, start, end);
	quickSort(vec, start, pi - 1);
	quickSort(vec, pi + 1, end);
}

